#include <iostream>
#include <string>
#include <vector>
#include <stack>


using namespace std;



class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;

        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();

            v.push_back(top->val);

            cur = top->right;
        }

        return v;
    }
};




class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, 
                    int& prei, int begini, int endi)
    {
        if (begini > endi)
            return nullptr;

        TreeNode* cur = new TreeNode(preorder[prei]);

        int rooti = 0;
        while (rooti < inorder.size())
        {
            if (inorder[rooti] == preorder[prei])
                break;
            rooti ++ ;
        }

        prei ++ ;
        cur->left = build(preorder, inorder, prei, begini, rooti - 1);
        cur->right = build(preorder, inorder, prei, rooti + 1, endi);
        return cur;
    }                
    

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int prei = 0;
        return build(preorder, inorder, prei, 0, inorder.size() - 1);
    }
};


class Solution {
public:
    bool findpath(TreeNode* root, TreeNode* n, stack<TreeNode*>& st)
    {
        if (root == nullptr)
            return false;

        st.push(root);
        if (root->val == n->val)
            return true;
        if (findpath(root->left, n, st))
            return true;
        if (findpath(root->right, n, st))
            return true;

        st.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> sp;
        stack<TreeNode*> sq;

        findpath(root, p, sp);
        findpath(root, q, sq);

        while (sp.size() > sq.size())
            sp.pop();
        while (sp.size() < sq.size())
            sq.pop();

        while (sq.top() != sp.top())
        {
            sq.pop();
            sp.pop();
        }

        return sp.top();
    }
};



class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* prev = nullptr;
        TreeNode* cur = root;
        vector<int> v;

        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();

            if (top->right == nullptr || top->right == prev)
            {
                prev = top;
                v.push_back(top->val);
                st.pop();
            }
            else 
            {
                cur = top->right;
            }
        }

        return v;
    }
};
